#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&&tqId=11218&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
[
    [a b c e]
    [s f c s]
    [a d e e ]
]
   矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
"""

# "ABCESFCSADEE",3,4,"ABCCED"

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        if not path:
            return False

        self.rows, self. cols = rows, cols
        self.matrix = matrix
        self.visited = [ [0 for c in range(cols)]  for r in range(rows)]
        self.path = path


        for r in range(rows):
            for c in range(cols):
                # if self.at(r,c) == path[0]:
                #     print('hit', r, c)
                ret = self.rec_find(r, c, 0)
                if ret:
                    return True
                # if self.at(r,c) == path[0]:
                #     print('hit', r, c)
                #     ret = self.rec_find(r, c, 0)
                #     if ret:
                #         return True

        return False

    def at(self, row, col):
        return self.matrix[row * self.cols + col]

    def rec_find(self, row, col, path_idx):
        if row >= self.rows or row < 0 or col >= self.cols or col < 0:
            return False

        if self.visited[row][col] == 1:
            return False

        # if self.matrix[row][col] != self.path[path_idx]:
        # if path_idx > len(self.path) - 1:
        #     return False

        if self.at(row, col) != self.path[path_idx]:
            return False

        if path_idx == len(self.path) - 1:
            print("end in", row, col)
            return True


        print('rec ', row, col)

        self.visited[row][col] = 1

        next_idx = path_idx + 1

        for pos in [(row, col+1), (row, col-1), (row-1, col), (row+1, col)]:
            # if self.rec_find(*pos, next_idx):
            if self.rec_find(pos[0], pos[1], next_idx):
                return True
            # self.rec_find(*pos, next_idx)
            # self.rec_find(*pos, next_idx)
            # self.rec_find(*pos, next_idx)

        self.visited[row][col] = 0


        return False


def test():
    s = Solution()
    m = [
        ["a", "b", "c", "e"],
        ["s", "f", "c", "s"],
        ["a", "d", "e", "e"],
    ]

    # ABCE
    # SFCS
    # ADEE

    r = s.hasPath("ABCESFCSADEE",3,4,"ABCCSEEDAS")
    # AAA
    # AAA
    # AAA
    # AAA
    # r = s.hasPath("AAAAAAAAAAAA",3,4,"AAAAAAAAAAAAA")

    # r = s.hasPath("ABCESFCSADEE",3,4,"ABCCED")

    # r = s.hasPath(m, 3, 4, 'bcced')
    print(r)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
